考虑判断一个字符串 $s$ 是否满足条件.

令 $G(s)_c$ 表示 $s$ 的以 $c$ 结尾的本质不同子序列个数, $G(s)_0$ 表示总的本质不同子序列个数. 那么若 $s = s' + a$ (字符串拼接), 则有

$$G(s)_c = \begin{cases} G(s')_0 & c = a, \\ G(s')_c & c \ne a, 0. \end{cases}$$

而

$$\begin{aligned} G(s)_0 &= 1 + \sum_{c \ne 0} G(s)_c \\ &= 1 + \sum_{c \ne 0, a} G(s')_c + G(s')_0 \\ &= 2G(s')_0 - G(s')_a \equiv G(s')_a \pmod{2} \end{aligned}$$

我们发现, 在模 $2$ 意义下在字符串后面加一个字符 $a$ 就是交换 $G$ 中 $0$ 和 $a$ 的值. 而最初的时候 $G(\varnothing)_c = [c=0]$, 所以只需要判断最后是否把 $0$ 换回 $0$.

那么我们在树上做的时候，只需要对每个结点 $i$ 和每个字符 $c$ 维护:

• 子树内有多少结点 $j$, 满足从 $i$ 走到 $j$ 会把 $G(s')_c$ 换到 $G(s)_0$;
• 子树内有多少结点 $j$, 满足从 $j$ 走到 $i$ 会把 $G(s')_0$ 换到 $G(s)_c$.

两棵子树合并的时候把对应位置乘起来统计答案, 往上走的时候交换两个位置的值即可.

更新:

可以发现连放两个相同字符等于不放. 所以可以把 i 到 j 改成 i 到根再到 j.

dfs 时可以维护当前点到根的置换. 这样就可以 $O(n)$ 求出每个点到根会把 $0$ 换成谁 (这也等价于从根到它会把谁换成 $0$). 最后统计答案即可.